跳至主要内容

LeetCode 141. Linked List Cycle (Easy)

題目連結​

https://leetcode.com/problems/linked-list-cycle/

解題技巧​

  • Fast-slow Pointers (快慢指針法) : 使用兩個不同速度的指針遍歷線性結構。在這題中，一個走一步，另一個走兩步。如果這個 linked list 有循環，兩個指針一定會相遇。

解法​

function hasCycle(head: ListNode | null): boolean {
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    while (fast && fast.next) {
        fast = fast.next.next;
        slow = slow!.next;
        if (slow === fast) {
            return true;
        }
    }
    return false;
};

Complexity :​

  • Time: O(n)，n 是 linked list 的節點數
  • Space: O(1)

解釋​

  1. 設定兩個指針，一個名為 fast，一個為 slow。剛開始都指向 head。
  2. 接著進入迴圈，每次迭代中，fast 指針每次向前移動兩個節點，而 slow 指針每次向前移動一個節點。在這邊用到 ! 來斷言 slow 不為空。如果 slow === fast，代表兩個點相遇，表示存在循環，因此返回 true。
  3. 當 fast 和 fast.next 為空代表 linked list 已經遍歷完畢，並不存在循環，因此返回 false